package com.leetcode.algorithm.y22.m09.w2;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 227. 基本计算器 II
 * 
 * https://leetcode.cn/problems/basic-calculator-ii/
 * 
 * @author jie.deng
 *
 */
class Question0227Solution01 {

	public int calculate(String s) {
		int len = s.length();
		int idx = 0;
		Deque<Integer> numStack = new ArrayDeque<>();
		Deque<Character> opStack = new ArrayDeque<>();
		char op = ' ';
		while (idx < len) {
			char ch = s.charAt(idx);
			if (ch >= '0' && ch <= '9') {
				StringBuilder builder = new StringBuilder();
				while (idx < len && s.charAt(idx) >= '0' && s.charAt(idx) <= '9') {
					builder.append(s.charAt(idx));
					idx++;
				}
				int a2 = Integer.parseInt(builder.toString());
				if (op == ' ') {
					numStack.offerLast(a2);
				} else {
					int a1 = numStack.pollLast().intValue();
					if (op == '*') {
						int num = a1 * a2;
						numStack.offerLast(num);
						op = ' ';
					} else {
						int num = a1 / a2;
						numStack.offerLast(num);
						op = ' ';
					}
				}
			} else if (ch == '+' || ch == '-') {
				opStack.offerLast(ch);
				idx++;
			} else if (ch == '*' || ch == '/') {
				op = ch;
				idx++;
			} else if (ch == ' ') {
				idx++;
			}
		}
		while (!opStack.isEmpty()) {
			char ch = opStack.pollFirst().charValue();
			int a1 = numStack.pollFirst().intValue();
			int a2 = numStack.pollFirst().intValue();
			if (ch == '+') {
				int num = a1 + a2;
				numStack.offerFirst(num);
			} else {
				int num = a1 - a2;
				numStack.offerFirst(num);
			}
		}
		return numStack.pollLast().intValue();
	}

}